У Ибрагима есть чёрная магическая
машинка. На ней есть три кнопки и табло. Табло может показывать не более чем
четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая множит
его на 3, вторая прибавляет к нему сумму его цифр, а третья вычитает из него 2.
В случае, если число становится отрицательным или превосходит 9999, машинка
ломается.
Ибрагим может нажимать кнопки в
любом порядке. Его интересует, как ему получить на табло число b после
некоторой последовательности нажатий, если сейчас машинка показывает a.
Помогите ему найти минимальное необходимое число нажатий.
Вход. В одной строке находятся два натуральных числа a и b
(1 ≤ a, b ≤ 9999).
Выход. Вывести
минимальное количество действий, за которое из числа a можно получить число b.
|
Пример
входа 1 |
Пример
выхода 1 |
|
14 15 |
2 |
|
|
|
|
Пример
входа 2 |
Пример
выхода 2 |
|
18 12 |
3 |
графы –
поиск в ширину
Анализ алгоритма
Для решения
задачи реализуем поиск в ширину из числа a. Если cur – текущее число,
то возможны следующие переходы:
·
умножение на 3: cur → cur * 3;
·
прибавление суммы цифр: cur → cur + sum(cur);
·
вычитание 2: cur → cur – 2;
По достижению
числа b останавливаем поиск.
Реализация алгоритма
Объявим рабочую
очередь d и массив кратчайших
расстояний dist. Значение dist[i] = -1, если число i еще не встретилось. Иначе dist[i] содержит наименьшее количество шагов, за которое из начального
числа можно получить число i.
#define MAX 10000
deque<int> d;
int dist[MAX];
Функция sum вычисляет сумму цифр числа n.
int sum(int
n)
{
if (n <
10) return n;
return sum(n
/ 10) + n % 10;
}
Функция inBounds проверяет, лежит ли значение n в границах [0..9999].
int inBounds(int n)
{
return (n
>= 0) && (n < MAX);
}
Функция go проверяет, можно ли из числа v перейти в to. Это возможно,
если to лежит в
промежутке [0..9999] и число to еще не встречалось (dist[to] = -1).
void go(int v, int to) // v -> to
{
if (inBounds(to) &&
dist[to] == -1)
{
Обновляем кратчайшее расстояние dist[to] и заносим число
to в очередь d.
dist[to] = dist[v] + 1;
d.push_back(to);
}
}
Функция bfs совершает поиск в ширину из числа а. Поиск останавливаем при достижении числа b.
void bfs(int
a, int b)
{
memset(dist,-1,sizeof(dist));
Для стартового числа a
положим dist[a] = 0. Занесем число a в
очередь d.
d.push_back(a); dist[a] = 0;
Поиск в ширину продолжаем пока очередь d не пустая.
while (!d.empty())
{
Извлекаем число cur из головы очереди. Если оно равно b,
то завершаем поиск.
int cur = d.front(); d.pop_front();
if (cur == b) break;
Совершим из cur три возможных перехода: в cur * 3, в cur + sum(cur) и в cur – 2.
go(cur, cur * 3);
go(cur, cur + sum(cur));
go(cur, cur - 2);
}
}
Основная часть программы. Читаем входные данные.
scanf("%d %d",&a,&b);
Запускаем поиск в ширину из числа a.
bfs(a,b);
Выводим ответ dist[b].
printf("%d\n", dist[b]);